{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Make All Array Elements Equal to 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组所有元素变成 1 的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的 <strong>正</strong>&nbsp;整数数组&nbsp;<code>nums</code>&nbsp;。你可以对数组执行以下操作 <strong>任意</strong>&nbsp;次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个满足&nbsp;<code>0 &lt;= i &lt; n - 1</code>&nbsp;的下标 <code>i</code>&nbsp;，将&nbsp;<code>nums[i]</code> 或者&nbsp;<code>nums[i+1]</code>&nbsp;两者之一替换成它们的最大公约数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回使数组 <code>nums</code>&nbsp;中所有元素都等于 <code>1</code>&nbsp;的 <strong>最少</strong>&nbsp;操作次数。如果无法让数组全部变成 <code>1</code>&nbsp;，请你返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>两个正整数的最大公约数指的是能整除这两个数的最大正整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,6,3,4]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们可以执行以下操作：\n",
    "- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。\n",
    "- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。\n",
    "- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。\n",
    "- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,10,6,14]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法将所有元素都变成 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-make-all-array-elements-equal-to-1](https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-make-all-array-elements-equal-to-1](https://leetcode.cn/problems/minimum-number-of-operations-to-make-all-array-elements-equal-to-1/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,6,3,4]', '[2,10,6,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a=[]\n",
    "        t=0\n",
    "        s=len(nums)\n",
    "        x=s\n",
    "        p=0\n",
    "        flag=False\n",
    "        for i in nums:\n",
    "            if i==1:\n",
    "                flag=True\n",
    "                p+=1\n",
    "        if flag:\n",
    "            return x-p\n",
    "        \n",
    "\n",
    "        while True:\n",
    "            t+=1\n",
    "            for i in range(s-1):\n",
    "                nums[i]=gcd(nums[i],nums[i+1])\n",
    "                if nums[i]==1:\n",
    "                    return t+x-1\n",
    "            nums.pop()\n",
    "            s-=1\n",
    "                \n",
    "            if s==1:\n",
    "                return -1\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if reduce(gcd, nums) > 1:\n",
    "            return -1\n",
    "        if min(nums) == 1:\n",
    "            return sum([1 for i in nums if i > 1]) \n",
    "        n = len(nums)\n",
    "        d = n - 1\n",
    "        for i in range(n - 1):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if tmp == 1:\n",
    "                    d = min(d, j - i)\n",
    "                    break\n",
    "        return d + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums)>1:\n",
    "            return -1\n",
    "        n=len(nums)\n",
    "        cnt1=sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "\n",
    "        min_size=n\n",
    "        for i in range(n):\n",
    "            g=0\n",
    "            for j in range(i,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    min_size=min(min_size,j-i)\n",
    "                    break\n",
    "        return min_size+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "                # 如果所有数的gcd>1，return -1\n",
    "        # 1如果有1，return n-count1\n",
    "        # 2如果没有1，return minsize-1+n-1\n",
    "        from math import gcd\n",
    "        if gcd(*nums)>1:return -1\n",
    "        cnt1=sum(num==1 for num in nums)\n",
    "        n=len(nums)\n",
    "        if cnt1:return n-cnt1\n",
    "        minsize=n\n",
    "        for i in range(n):\n",
    "            g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize,j-i+1)\n",
    "                    break \n",
    "        return minsize+n-2\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1 != 0:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        minn=9999999\n",
    "        if 1 in nums:\n",
    "            return len(nums)-nums.count(1)\n",
    "        l=len(nums)\n",
    "        temp2=0\n",
    "        for i in range(l-1):\n",
    "            temp=nums[i]\n",
    "            for j in range(i+1,l):\n",
    "                if math.gcd(temp,nums[j])==1:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "                    if j-i<minn:\n",
    "                        minn=j-i\n",
    "                    temp2=-1\n",
    "                else:\n",
    "                    temp=math.gcd(temp,nums[j])\n",
    "            if temp2==0:\n",
    "                return -1\n",
    "        return l+minn-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) >1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n-cnt1\n",
    "        minsize = n\n",
    "        for i in range(n):\n",
    "            g =  0\n",
    "            for j in range(i,n):\n",
    "                g = gcd(g,nums[j])\n",
    "                if g == 1:\n",
    "                    minsize = min(minsize,j-i)\n",
    "                    break\n",
    "        return minsize+n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        # 质因数分解 \r\n",
    "        # 如果 所有数字都有相同质因数那么返回 -1 \r\n",
    "        # 否则返回最快变1操作数 + (len(num1) - 1)\r\n",
    "\r\n",
    "        # 我以为随便选两个数，，，，绷不住了 \r\n",
    "        # \r\n",
    "        n = len(nums)\r\n",
    "        # def divx(x: int) -> List[int]:\r\n",
    "        #     dx = []\r\n",
    "        #     for i in range(2, isqrt(x) + 1):\r\n",
    "        #         if x % i == 0:\r\n",
    "        #             dx.append(i)\r\n",
    "        #             while x % i == 0:\r\n",
    "        #                 x //= i \r\n",
    "        #     if x > 1:\r\n",
    "        #         dx.append(x)\r\n",
    "        #     return dx\r\n",
    "                \r\n",
    "        # res = inf \r\n",
    "        # for x in nums:\r\n",
    "        #     d = divx(x)\r\n",
    "        #     dp = [[inf] * (1 << len(d)) for _ in range(n + 1)]\r\n",
    "        #     for i in range(n + 1):\r\n",
    "        #         dp[i][0] = 0\r\n",
    "        #     for i in range(n):\r\n",
    "        #         m = 0\r\n",
    "        #         for k, y in enumerate(d):\r\n",
    "        #             if nums[i] % y == 0:\r\n",
    "        #                 m |= (1 << k) \r\n",
    "        #         for j in range(1 << (len(d))):\r\n",
    "        #             dp[i + 1][j] = min(dp[i][j], dp[i][j&m] + 1)\r\n",
    "        #     if dp[-1][- 1] == inf:\r\n",
    "        #         return -1 \r\n",
    "        #     res = min(res, dp[-1][-1] + (n - 1)) \r\n",
    "        #     print(dp)\r\n",
    "        # return res if res != inf else -1 \r\n",
    "        cnt = sum(x == 1 for x in nums)\r\n",
    "        if cnt:\r\n",
    "            return n - cnt \r\n",
    "        \r\n",
    "        res = inf\r\n",
    "        for i in range(n):\r\n",
    "            g = nums[i]\r\n",
    "            for j in range(i, n):\r\n",
    "                g = gcd(g, nums[j])\r\n",
    "                if g == 1:\r\n",
    "                    res = min((j - i) + (n - 1), res)\r\n",
    "        return res if res != inf else -1 \r\n",
    "    \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        tmp = nums.copy()\n",
    "        ans = n-nums.count(1)\n",
    "        while tmp:\n",
    "            for i in range(len(tmp)-1):\n",
    "                tmp[i] = gcd(tmp[i], tmp[i+1])\n",
    "                if tmp[i] == 1:\n",
    "                    return ans\n",
    "            ans += 1 # length of [i,j] interval (that make 1 happen) + 1\n",
    "            tmp.pop()\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    # 这里本来是 j-i+1，把 +1 提出来合并到 return 中\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        cnt1 = sum(num == 1 for num in nums)\n",
    "        \n",
    "        if cnt1 > 0:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_cnt = inf\n",
    "\n",
    "        for i in range(n-1):\n",
    "            gcd_res = nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                gcd_res = gcd(nums[j], gcd_res)\n",
    "                \n",
    "                if gcd_res == 1:\n",
    "                    min_cnt = min(min_cnt, j - i)\n",
    "                    break\n",
    "                    \n",
    "        return n + min_cnt - 1 if min_cnt < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, A: List[int]) -> int:\n",
    "        return len(A) - A.count(1) if 1 in A else -1 if gcd(*A) != 1 else len(A) + min(j - i for i, j in combinations(range(len(A) + 1), 2) if 1 == gcd(*A[i: j])) - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            while b:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        min_len = float('inf')\n",
    "        n = len(nums)\n",
    "        one_cnt = nums.count(1)\n",
    "        if one_cnt:\n",
    "            return n - one_cnt\n",
    "        for i in range(n - 1):\n",
    "            g = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_len = min(min_len, j - i + 1)\n",
    "        return n - 1 + (min_len - 1) if min_len != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        n_one = nums.count(1)\n",
    "        if n_one:\n",
    "            return n - n_one\n",
    "        \n",
    "        min_len = n\n",
    "        for i in range(n):\n",
    "            min_gcd = 0\n",
    "            for k in range(i,n):\n",
    "                min_gcd = gcd(min_gcd, nums[k])\n",
    "                if min_gcd == 1:\n",
    "                    min_len = min(min_len, k - i)\n",
    "                    break\n",
    "            \n",
    "            if min_len == 1:\n",
    "                break\n",
    "\n",
    "        return min_len + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a = gcd(a,nums[j])\n",
    "                if a == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        a1 = 0\n",
    "        tmp = nums[0]\n",
    "        if nums[0]==1:\n",
    "            a1+=1\n",
    "        for i in nums[1:]:\n",
    "            tmp=gcd(tmp,i)\n",
    "            if i==1:\n",
    "                a1+=1\n",
    "        if tmp!=1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        if a1>0:\n",
    "            return n-a1\n",
    "        res = n\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                t = gcd(t,nums[j])\n",
    "                if t==1:\n",
    "                    res=min(res,j-i+1)\n",
    "        return n+res-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        t = sum(1 for i in nums if i == 1)\n",
    "        if t:\n",
    "            return n - t\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        a = nums.copy()\n",
    "        for t in range(1, n):\n",
    "            a.pop()\n",
    "            for i, c in enumerate(a):\n",
    "                a[i] = gcd(c, nums[i + t])\n",
    "                if a[i] == 1:\n",
    "                    return n + t - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt_1 = 0\n",
    "        for num in nums:\n",
    "            cnt_1 += (num == 1)\n",
    "        if cnt_1 > 0:\n",
    "            return n - cnt_1\n",
    "        l = 1\n",
    "        f = copy.deepcopy(nums)\n",
    "        while l < n:\n",
    "            for i in range(0, n - l):\n",
    "                f[i] = gcd(f[i], nums[i + l])\n",
    "                if f[i] == 1:\n",
    "                    return n + l - 1\n",
    "            l += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def gcd(x, y):\n",
    "            while y:\n",
    "                tmp = y\n",
    "                y = x % y \n",
    "                x = tmp \n",
    "            return x \n",
    "        cnt = nums.count(1)\n",
    "        def check(start, end):\n",
    "            g = nums[start]\n",
    "            for i in range(start + 1, end + 1):\n",
    "                g = gcd(g, nums[i])\n",
    "            return g == 1 \n",
    "        if cnt > 0:\n",
    "            return n - cnt \n",
    "        l = 0\n",
    "        res = float('inf')\n",
    "        for r in range(n):\n",
    "            while l < r and check(l, r):\n",
    "                res = min(res, r - l + n - 1)\n",
    "                l += 1 \n",
    "        return res if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果所有的相邻的两个数都大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一个连续子数组，对其 gcd 得到第一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:# 从 i 到 j 的子数组 gcd 是 1， 那么我们就先对其 gcd，操作数为 cnt，再加上扩展的操作数为 len(nums) - 1\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break # 提前退出\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        a = []  # [GCD，相同 GCD 闭区间的右端点]\n",
    "        for i, x in enumerate(nums):\n",
    "            a.append([x, i])\n",
    "\n",
    "            # 原地去重，因为相同的 GCD 都相邻在一起\n",
    "            j = 0\n",
    "            for p in a:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if a[j][0] != p[0]:\n",
    "                    j += 1\n",
    "                    a[j] = p\n",
    "                else:\n",
    "                    a[j][1] = p[1]\n",
    "            del a[j + 1:]\n",
    "\n",
    "            if a[0][0] == 1:\n",
    "                # 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中\n",
    "                min_size = min(min_size, i - a[0][1])\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 原本如果数组里有1，那么最少操作数是 n - cnt\n",
    "        # 如果没有1，那么就最短的gcd为1的子数组构造出一个1\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 如果相邻的两个数大于 1，且 gcd 都大于 自身，意味着 gcd 不会更小，那么返回 -1\n",
    "        # 否则找到一对，进行 gcd 直到等于 1，我们得到了一个 1\n",
    "        # 以题目的 [2,6,3,4] 为例，我们得到了 [2, 6, 3, 1]\n",
    "        # 接下来用 1 和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        # 特殊地，如果数组中已经有 1 了，那么直接和其他的非 1 每个进行一次 gcd 即可，次数是最少的\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            cnt += num == 1\n",
    "        if cnt > 0: return len(nums) - cnt\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            g = nums[i]\n",
    "            cnt = 0\n",
    "            for j in range(i+1, len(nums)):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                cnt += 1\n",
    "                if g == 1:\n",
    "                    ans = min(ans, len(nums) - 1 + cnt)\n",
    "                    break\n",
    "        return -1 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=inf\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                ans=1\n",
    "                break\n",
    "            else:\n",
    "                g=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                g=gcd(g,nums[j])\n",
    "                if g==1: ans=min(ans,j-i+1)\n",
    "        print(ans)\n",
    "        if ans==inf:return -1\n",
    "        elif ans==1: return n-nums.count(1)\n",
    "        elif ans==2: return n\n",
    "        else: return ans-2+n\n",
    "        #n=4, ans=2\n",
    "        #n=3, ans=3\n",
    "        #n=5, ans=3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        arr=nums\n",
    "        st=[]\n",
    "        min_size=n\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=gcd(st[j][0],a)\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "            nst.append([a,i])\n",
    "            for j in range(len(nst)-1):\n",
    "                v,s,e=nst[j][0],nst[j][1],nst[j+1][1]-1\n",
    "            st=nst\n",
    "            if st[0][0]==1:\n",
    "                min_size=min(min_size,i-(st[1][1]-1)+1)\n",
    "            #print(st)\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return min_size + n - 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(a:int,b:int)->int:\n",
    "            while b != 0:\n",
    "                a,b = b,a%b\n",
    "            return a\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        a = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        dis = inf\n",
    "        for i in range(n):\n",
    "            ones += 1 if nums[i] == 1 else 0\n",
    "            a[i][i] = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                a[i][j] = gcd(a[i][j-1],nums[j])\n",
    "                if a[i][j] == 1:\n",
    "                    dis = min(dis,j-i)\n",
    "        if ones:\n",
    "            return n - ones\n",
    "        elif dis == inf:\n",
    "            return -1\n",
    "        else:\n",
    "            return n + dis - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if 1 in nums:\n",
    "            return len(nums) - nums.count(1)\n",
    "        n = len(nums)\n",
    "        if reduce(gcd, nums) != 1:\n",
    "            return -1\n",
    "        for l in range(2, 51):\n",
    "            for i in range(n - l + 1):\n",
    "                if reduce(gcd, nums[i: i + l]) == 1:\n",
    "                    return l + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            g = math.gcd(g,num)\n",
    "            if num == 1:\n",
    "                cnt+=1\n",
    "        if g!=1:\n",
    "            return -1\n",
    "        \n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        minsize = n+1\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i,n):\n",
    "                g = math.gcd(g, nums[j])\n",
    "                if g==1:\n",
    "                    minsize=min(minsize, j-i+1)\n",
    "        return minsize + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(num1, num2):\n",
    "            if(num1 < num2):\n",
    "                num1, num2 = num2, num1\n",
    "            if(num1 % num2 == 0):\n",
    "                return num2\n",
    "            return gcd(num2, num1%num2)\n",
    "        n = len(nums)\n",
    "        ones = 0\n",
    "        for i in range(n):\n",
    "            if(nums[i] == 1):\n",
    "                ones += 1\n",
    "        if(ones > 0):\n",
    "            return n - ones\n",
    "        min_size = float('inf')\n",
    "        for i in range(n):\n",
    "            tmp = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                tmp = gcd(tmp, nums[j])\n",
    "                if(tmp == 1):\n",
    "                    min_size = min(min_size, j-i+1)\n",
    "        if(min_size == float('inf')):\n",
    "            return -1\n",
    "        else:\n",
    "            return n - 1 + min_size - 1\n",
    "                \n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                count += 1\n",
    "        if count > 0:\n",
    "            return len(nums) - count\n",
    "        minlength = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if gcd(*nums[i:j]) == 1:\n",
    "                    minlength = min(minlength, j - i)\n",
    "        return minlength + len(nums) - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for nu in nums:\n",
    "            if nu == 1:\n",
    "                cnt += 1\n",
    "        if cnt != 0:\n",
    "            return n - cnt\n",
    "        ans = 100\n",
    "        for i in range(n):\n",
    "            res = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                res = gcd(res, nums[j])\n",
    "                if res == 1:\n",
    "                    ans = min(ans, j - i + n - 1)\n",
    "                    break\n",
    "        if ans == 100:\n",
    "            return -1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "\n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i)\n",
    "                    break\n",
    "        return min_size + n - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1 :\n",
    "            return -1\n",
    "        n = len(nums)\n",
    "        cnt1 = sum(x == 1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        min_size = n\n",
    "        for i in range(n):\n",
    "            g = 0\n",
    "            for j in range(i, n):\n",
    "                g = gcd(g, nums[j])\n",
    "                if g == 1:\n",
    "                    min_size = min(min_size, j - i + 1)\n",
    "                    break\n",
    "        \n",
    "        return min_size + n - 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "        n, cnt1 = len(nums), sum(x==1 for x in nums)\n",
    "        if cnt1:\n",
    "            return n - cnt1\n",
    "        \n",
    "        g, min_size = [], n\n",
    "        for i, x in enumerate(nums):\n",
    "            g.append([x, i])\n",
    "\n",
    "            j = 0\n",
    "            for p in g:\n",
    "                p[0] = gcd(p[0], x)\n",
    "                if g[j][0] == p[0]:\n",
    "                    g[j][1] = p[1]\n",
    "                else:\n",
    "                    j += 1\n",
    "                    g[j] = p\n",
    "            del g[j+1:]\n",
    "\n",
    "            if g[0][0] == 1:\n",
    "                min_size = min(min_size, i-g[0][1]+1)\n",
    "        return min_size + n - 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def gcd(x,y):\n",
    "            if y%x==0 or x%y==0:\n",
    "                return min(x,y)\n",
    "            return gcd(max(x,y)%min(x,y),min(x,y))\n",
    "        res=nums[0]\n",
    "        for num in nums:\n",
    "            res=gcd(res,num)\n",
    "        if res>1:\n",
    "            return -1\n",
    "        cnt=0\n",
    "        for num in nums:\n",
    "            if num==1:\n",
    "                cnt+=1\n",
    "        if cnt>0:\n",
    "            return n-cnt\n",
    "        \n",
    "        def check(x):\n",
    "            for i in range(n):\n",
    "                res=nums[i]\n",
    "                for j in range(1,x):\n",
    "                    if i+j<n:\n",
    "                        res=gcd(res,nums[i+j])\n",
    "                        if res==1:\n",
    "                            return True\n",
    "            return False\n",
    "                \n",
    "\n",
    "        \n",
    "        left,right=n-1,2*n-1\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid-n+1):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if gcd(*nums) > 1:\n",
    "            return -1\n",
    "\n",
    "        cnt1 =sum(x == 1 for x in nums)        \n",
    "\n",
    "        if cnt1:\n",
    "            return n -cnt1\n",
    "        min_size = n\n",
    "        g = []\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            g.append([x,i])\n",
    "            ## 相同的 gcd 在一起\n",
    "            j = 0\n",
    "            for p in g :\n",
    "                p[0] = gcd(p[0],x)\n",
    "                if g[j][0]!=p[0]:\n",
    "                    j +=1\n",
    "                    g[j] = p\n",
    "                else:\n",
    "                    g[j][1] = p[1]\n",
    "            del g[j+1:]\n",
    "            if g[0][0] ==1:\n",
    "                min_size =min(min_size,i-g[0][1])\n",
    "        \n",
    "        return min_size +n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, nums: List[int]) -> int:\r\n",
    "        if reduce(gcd, nums) != 1:\r\n",
    "            return -1\r\n",
    "        h = Counter(nums)\r\n",
    "        if h[1]:\r\n",
    "            return len(nums) - h[1]\r\n",
    "        for i in range(2, len(nums) + 1):\r\n",
    "            for j in range(0, len(nums) - i + 1):\r\n",
    "                if reduce(gcd, nums[j:j + i]) == 1:\r\n",
    "                    return len(nums) + i - 2\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ml=n=len(nums)\n",
    "        one=0\n",
    "        yes=False\n",
    "        for i in range(n):\n",
    "            if nums[i]==1:\n",
    "                one+=1\n",
    "            g=nums[i]\n",
    "            j=i\n",
    "            while g!=1 and j<n:\n",
    "                g=gcd(g,nums[j])\n",
    "                j+=1\n",
    "            if g==1:\n",
    "                ml=min(ml,j-i)\n",
    "                yes=True\n",
    "        if not yes :return -1\n",
    "        print(one,ml,n)\n",
    "        if ml==0:\n",
    "            return n-one\n",
    "        else:\n",
    "            return n+ml-2\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
